package linkedlist;

/**
 * Created with IntelliJ IDEA.
 * Description: 牛客 CM11 链表分割
 * https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
 * User: Li_yizYa
 * Date: 2025—04—09
 * Time: 22:24
 */
public class Solution7 {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(1);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = null;
        ListNode ret = partition(node1, 5);
        while (ret != null) {
            System.out.print(ret.val + " ");
            ret = ret.next;

        }
    }

    private static ListNode partition(ListNode pHead, int x) {
        if (pHead == null || pHead.next == null) {
            return pHead;
        }
        ListNode cur = pHead;
        ListNode as = null; // 记录比 x 大的
        ListNode ae = null;
        ListNode bs = null; // 记录比 x 小的
        ListNode be = null;

        while (cur != null) {
            if (cur.val >= x) {
                if (as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                    ae = ae.next;
                }
            } else {
                if (bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = be.next;
                }
            }
            cur = cur.next;
        }

        if (bs == null) {
            return as;
        }
        be.next = as;
        if (as != null) {
            ae.next = null;
        }
        return bs;
    }
}
